1. Field of the Invention
The present invention relates in general to an error correction code decoder and a method thereof, and in particular to an error correction code decoder and a method thereof capable of effectively implementing error correction using a small size decoder with two kinds of erasures in order to maximize features of the product code.
2. Description of the Conventional Art
Conventionally, designing a stable circuit capable of sending, receiving and storing digital data free of errors is extremely costly. Thus, in general, circuits are designed for permitting some data errors and in compensation for this, the original data is encoded/decoded by a predetermined algorithm for detecting or correcting the aforementioned errors. Here, the code in which the original data is encoded is called an error correction code, and since this error correction code is arranged to be in a certain order between each of the symbols which is consisting of codes, the errors which might happen during sending, receiving, storing, or restoring the data are detected or corrected during decoding. In addition, for detecting/correcting more data errors during decoding, the code length of the error correction code becomes longer, and the size of the encoder/decoder which is used becomes larger. Therefore, during the design of the circuit, the error detection/correction capability and the size of the encoder/digital decoder should be considered.
To correct the error during decoding, despite what kind of error correction code is used, the possible error location(which symbol has the error?) in the received/restored data and the error size(what is The original value need to be obtained?) must be determined. Therefore, for error correction, each data needs two equations since each error has two kinds of information, error location and size.
However, depending on circumstances, there may be cases where at least it is known that the specific symbol of a code is not correct, although the actual value is known. That is, in case that the value of the received/restored data is completely unexpected or if serious noises are mixed therein, the corresponding values will be unreliable. This is also a kind of an error, but since the location thereof is known, for computing the size, only one equation is needed. This is an erasure. Therefore, since the capacity of error correction of the error correction code is decided according to how many equations can be used, in case that the same error correction code is used, if the information of the erasure may be transferred to the decoder, the total sum of the error which can be corrected by the decoder will increase.
In addition, the errors which occur during sending, receiving and storing are classified into two kinds: a sporadic error which occurs with a certain probability and a concatenated error which a couple or a couple of tens of symbols consequently occur in error. The error correction code decoder is strong against sporadic error but weak against concatenated error, so in order to correct concatenated errors, a very large size decoder is needed. For achieving a higher error detection/correction capability with a small size encoder/decoder, conventionally, there had been introduced the concatenated code to encode the original data more than twice using different methods. One method is a product code which is to array the original data and then to encode/decode the arrayed data once in each horizontal and vertical directions.
The product code, as shown in FIG. 1, is designed to be strong for concatenated error by adding the parities Pmk and Qln in a horizontal and vertical direction for the original data Smn, here, Rlk is a parity of C1 code and a parity of C2 code. In FIG. 1, if we assume that the code in a horizontal direction is C1 and the code in a vertical direction is C2, the product code which consists of C1 and C2 is designed in order that the concatenated error in one direction may not be the sporadic error in a different direction, so that with a small size of the decoder, the decoding is effectively implemented.
The conventional decoder, as shown in FIG. 2, includes a first-in, first-out memory 1 for temporally storing the received/restored data; a syndrome calculator 2 for computing a syndrome which is a result value from the received/restored data; an erasure calculator 3 for computing an erasure location equation by counting the number of erasures from the 1 bit flag; an error location/size calculator 4 for computing the error location and size by using the erasure location equation of the erasure calculator 3; and a result output section 5 for outputting the corrected data and the flag after correcting the error mixed into the data inputted from the first-in, first-out memory 1 according to an operation of the output signal of the error location/size calculator 4.
The operative description of the conventional decoder will now be explained with reference to FIG. 3 and FIG. 4.
To begin with, when a received/restored 1 bit flag is inputted into the erasure calculator 3, the erasure calculator 3 detects whether the erasure occurred based upon the inputted flag. Here, if the erasure occurred, it is also determined whether the total number of the occurred erasure is in the range of error correction of the decoder. If the number of the erasure is in the range of the error correction of the decoder, the erasure calculator 3 computes the erasure location and outputs it to the error location/size calculator 4.
Meanwhile, the received/restored data is temporally stored into the first-in, first-out memory 1 and inputted into the syndrome calculator 2. At this time, the syndrome calculator 2 calculates the received/restored data containing mixed errors and outputs a specific result value of the errors, called the syndrome, and outputs the syndrome which is a result value of its inherent error and outputs it to the error location/size calculator 4.
Thereafter, the error location/size calculator 4 calculates the syndrome value and outputs an error location equation. At this time, the error location/size calculator 4 includes the erasure location the erasure calculator 3 into the error location equation. Thereafter, the error location/size calculator 4 computes the error size equation using the aforementioned error location equation and computes the above error location equation and the error size equation if the two computed equation are in the range of the error correction of the decoder, so that the error location/size are outputted therefrom.
The result output section 5 corrects the error of the data inputted from the first-in, first-out memory 1 according to the error location/size computed at the error location/size calculator 4, and applies 1 bit data when the error correction is completed, which implies that the current data is reliable, to each of the data and outputs them. However, in case that the detected errors are judged as not being in the range of the error correction of the decoder by checking the number of the erasure, or the detected error is judged as not being in the range of the error correction of the decoder by checking the error location equation and the error size equation at the error location/size calculator 4, the result output section 5 outputs the output data of the first-in, first-out memory 1 without correction and adds a 1 bit flag, which implies that the current data is not reliable, to each of the data and outputs them.
Whether the data which the result output section 5 outputs is reliable or not is indicated by whether 1 bit is added to each of the data or not. If the flag bit of the inputted data is set as 1, the erasure calculator 3 judges the data as not reliable. In addition, if the error location/size calculator 4 judges that the current data is not reliable, the current data for flag bit is set to as 1. Here, the data which the flag is set 1 indicates an erasure and the data for which the set to flag is set zero indicates normal data. The erasure which occurs as a result of the decoding, is used at the second decoding in the product code.
As these decoding process are repeatedly implemented, the data errors are corrected. If the data shown in FIG. 4A are received/restored, C1 code is decoded as shown in FIG. 4B. Here, since the fourth row shown in FIG. 4B is not in the range of the error correction of the decoder, all are processed as erasures. In addition, when C2 code is decoded, erasures of the fourth row are recognized as individual erasures, and as the decoding is implemented, the errors are corrected sufficiently. As described above, when the product code is decoded in the order "Receiving/restoring.fwdarw.C1 decoding.fwdarw.C2 decoding," the following differences occur between the erasure during the receiving/restoring of the data and the erasure during the decoding of C1 code. That is, the erasure which occurs during the receiving/restoring of the data are the actually occurred errors, however, to process each of the data of the fourth row as shown in FIG. 4B as an erasure implies that all the data of the corresponding code are not correct. If the number of erasures occurred during receiving/restoring data is not in the range of the error correction, the number of the erasure increases as shown in FIG. 4A. If the number of the increased erasures are in the range of the error correction, there are no problems. Otherwise, due to the erasures increased during decoding of C1 code, C2 code might fail to correct the errors of the data. That is, according to the conventional decoder, if the number of the errors increase beyond a predetermined limitation due to the characteristics of the products code, decoding of data will not be implemented despite the fact that data might have been be likely decoded.